Однородные системы линейных уравнений

Система линейных уравнений называется **однородной**, если свободные члены всех уравнений системы нулевые: $$\begin{cases} a_{11}x_{1} + a_{12}x_{2} + \dots a_{1n}x_{n} = 0 \\ a_{21}x_{1} + a_{22}x_{2} + \dots a_{2n}x_{n} = 0 \\ \dots\dots\dots\dots\dots\dots\dots\dots\dots \\ a_{k1}x_{1} + a_{k2}x_{2} + \dots a_{kn}x_{n} = 0 \end{cases}$$ По теореме Кронекера-Капелли однородная система всегда совместна.

Если $\mathbf{x}_{0}$ - некоторое (**частное**) решение системы $A\mathbf{x} = \mathbf{b}$, то вектор-столбец $\mathbf{x}_{1}$ будет решением $A\mathbf{x} = \mathbf{b}$ $\iff$ $\mathbf{x}_{1} = \mathbf{x}_{0} + \mathbf{y}$, где $\mathbf{y}$ - решение соответствующей однородной системы $A\mathbf{x} = \mathbf{0}$

$\Large\implies$ $\mathbf{x}_{1}$ - решение системы $A\mathbf{x} = \mathbf{b}$, положим $\mathbf{y} := \mathbf{x}_{1} - \mathbf{x}_{0}$. Тогда: $$A\mathbf{y} = A(\mathbf{x}_{1} - \mathbf{x}_{0}) = A\mathbf{x}_{1} - A\mathbf{x}_{0} = \mathbf{b} - \mathbf{b} = \mathbf{0}$$ Значит $\mathbf{y}$ - решение однородной системы $A\mathbf{x} = 0$ и $\mathbf{x}_{1} = \mathbf{x}_{0} + \mathbf{y}$. $\Large\impliedby$ $\mathbf{x}_{1} = \mathbf{x}_{0} + \mathbf{y}$, где $\mathbf{y}$ - решение $A\mathbf{x} = \mathbf{0}$. Тогда: $$A\mathbf{x}_{1} = A(\mathbf{x}_{0} + \mathbf{y}) = A\mathbf{x}_{0} + A\mathbf{y} = \mathbf{b} + \mathbf{0} = \mathbf{b}$$ Отсюда $\mathbf{x}_{1}$ - решение системы $A\mathbf{x} = \mathbf{b}$ $~~~\square$

Доказанное показывает, что для нахождения **всех** решений $A\mathbf{x} = \mathbf{b}$ достаточно найти какое-нибудь одно **частное** решение этой системы, а затем найти **общее решение** системы $A\mathbf{x} = \mathbf{b}$ как сумму **частного** решения и общего решения однородной системы: $$\mathbf{x}_{1} = \mathbf{x}_{0} + \mathbf{y}$$ где $\mathbf{x}_{1}$ - решение $A\mathbf{x} = \mathbf{b}$, $\mathbf{x}_{0}$ - частное решение $A\mathbf{x} = \mathbf{b}$, $\mathbf{y}$ - общее решение однородной системы.

Множество решений однородной системы $A\mathbf{x} = \mathbf{0}$ образует подпространство в пространстве столбцов.

Если $A$ - $k\times n$-матрица, то правило $\mathcal{A}(\mathbf{x}) := A\mathbf{x}$ определяет линейный оператор $\mathcal{A}: V_{1} \to V_{2}$ из пространства столбцов высоты $n$ в пространство столбцов высоты $k$. Следовательно, множество решений системы $A\mathbf{x} = 0$ будет **ядром** оператора $\mathcal{A}$, а значит и подпространством. $~~~\square$

Если пространство решений однородной системы ненулевое, то любой базис этого пространства называется **фундаментальной системой решений**

Если $\mathbf{y}_{1}, \mathbf{y}_{2}, \dots, \mathbf{y}_{d}$ - фундаментальная система решений системы $A\mathbf{x} = \mathbf{0}$, то любое решение $\mathbf{y}$ этой системы однозначно представимо в виде: $$\mathbf{y} = c_{1} \mathbf{y}_{1} + c_{2} \mathbf{y}_{2} + \dots + c_{d} \mathbf{y}_{d} ~~~~~(*)$$ Выражение $(*)$ принято называть **общим решением** системы $A\mathbf{x} = \mathbf{0}$

Размерность пространства решений системы $A\mathbf{x} = \mathbf{0}$ равна $n - r$, где $n$ - число неизвестных в системе, а $r$ - ранг матрицы $A$

Снова рассмотрим линейный оператор $\mathcal{A}: V_{1} \to V_{2}$., $\mathcal{A} := A\mathbf{x}$ и применим к нему теорему о ранге и дефекте: сумма ранга ($\mathrm{dim}(\mathrm{Im}~\mathcal{A})$) и дефекта ($\mathrm{dim}~(\mathrm{Ker}~\mathcal{A})$) равна размерности пространства столбцов высоты $n$, т.е $n$. Так как ранг линейного оператора совпадает с рангом его матрицы, $r(\mathcal{A}) = r$. Ядро оператора $\mathcal{A}$ - пространство решений системы, поэтому его размерность равна $d(\mathcal{A}) = n - r$. $~~~\square$

Рассмотрим произвольную однородную систему: $$\begin{cases} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1n} x_{n} = 0 \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2n} x_{n} = 0 \\ \dots\dots\dots\dots\dots\dots\dots\dots\dots\dots \\ a_{k1} x_{1} + a_{k2} x_{2} + \dots + a_{kn} x_{n} = 0 \end{cases}$$ Если ранг её матрицы $A$ $r = n$, то размерность пространства решений равна $0$, а значит фундаментальной системы решений нет (единственное решение - $0$). Поэтому будем рассматривать случай $r < n$ В силу теоремы о ранге в $A$ есть $r$ линейно независимых строк. Переставим уравнения так, чтобы первые $r$ строк были линейно независимы, а последующие, так как они линейно выражаются через предыдущие, вычеркнем, получим: $$\begin{cases} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1n} x_{n} = 0 \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2n} x_{n} = 0 \\ \dots\dots\dots\dots\dots\dots\dots\dots\dots\dots \\ a_{r1} x_{1} + a_{r2} x_{2} + \dots + a_{rn} x_{n} = 0 \end{cases}$$ Обозначим матрицу этой системы через $A'$. Ясно, что $r(A') = r$, поэтому у $A'$ есть $r$ линейно независимых столбцов. **Переименуем переменные** и перенесём линейно зависимые столбцы в правую часть, получим: $$\begin{cases} b_{11} y_{1} + b_{12} y_{2} + \dots + b_{1r} y_{r} = -b_{1~r+1} y_{r+1} - b_{1~r+2} y_{r+2} - \dots - b_{1n} y_{n} \\ b_{21} y_{1} + b_{22} y_{2} + \dots + b_{2r} y_{r} = -b_{2~r+1} y_{r+1} - b_{2~r+2} y_{r+2} - \dots - b_{2n} y_{n} \\ \dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots \\ b_{r1} y_{1} + b_{r2} y_{2} + \dots + b_{rr} y_{r} = -b_{r~r+1} y_{r+1} - b_{r~r+2} y_{r+2} - \dots - b_{rn} y_{n} \end{cases} ~~~~~(\dagger)$$ Неизвестные $y_{r+1}, \dots, y_{n}$ называются **свободными**, а неизвестные $y_{1}, y_{2}, \dots, y_{r}$ - **связанными**. В матричном виде систему $(\dagger)$ можно записать как $B\mathbf{y} = \mathbf{c}$, где $B = (b_{ij})_{r\times r}$ - матрица при неизвестных $y_{1}, \dots, y_{r}$ и $$\mathbf{y} := \begin{pmatrix}y_{1}\\\vdots\\y_{r}\end{pmatrix},~~~ c := \begin{pmatrix} -b_{1~r+1}y_{r+1} - \dots - b_{1n}y_{n} \\ \vdots \\ -b_{r~r+1}y_{r+1} - \dots - b_{rn}y_{n} \end{pmatrix}$$ Из построений матрицы $B$ ясно, что она обратима. Умножая $B\mathbf{y} = \mathbf{c}$ слева на $B^{-1}$, получаем единственное решение системы $(*)$ в виде $\mathbf{y} = B^{-1}\mathbf{c}$. Переходя к координатам, имеем: $$\begin{cases} y_{1} = c_{1~r+1}y_{r+1} + \dots + c_{1n}y_{n} \\ y_{2} = c_{2~r+1}y_{r+1} + \dots + c_{2n}y_{n} \\ \dots\dots\dots\dots\dots\dots\dots\dots\dots \\ y_{r} = c_{r~r+1}y_{r+1} + \dots + c_{rn}y_{n} \end{cases} ~~~~~(*)$$ Для $i = \overline{r+1, n}$ придадим свободной переменной $y_{i}$ значение $1$, а всем остальным неизвестным - $0$. Вычислив по $(*)$ значения связанных переменных, получим $n-r$ решений: $$\mathbf{y}_{1} := \begin{pmatrix} c_{1~r+1} \\ \vdots \\ c_{r~r+1} \\ 1 \\ \vdots \\ 0 \end{pmatrix}, \dots,~ \mathbf{y}_{n-r} := \begin{pmatrix} c_{1n} \\ \vdots \\ c_{rn} \\ 0 \\ \vdots \\ 1 \end{pmatrix}$$ Утверждается, что эти решения образуют фундаментальную систему решений для системы $(\dagger)$. Действительно, их число равно размерности $n-r$ пространства решений системы, а сами эти решения линейно независимы, что легко увидеть, если записать их в матрицу: $$~~~~~~~\mathbf{y}_{1}~~~~~~~~ \mathbf{y}_{2}~~~~~ \dots~~~~~ \mathbf{y}_{n-r} \atop \begin{pmatrix} c_{1~r+1} & c_{1~r+2} & \dots & c_{1n} \\ c_{2~r+1} & c_{2~r+2} & \dots & c_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{r~r+1} & c_{r~r+2} & \dots & c_{rn} \\ 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 \end{pmatrix}$$ Переход к исходным неизвестным $x_{1}, \dots, x_{n}$ означает перестановку строк данной матрицы. При этом столбцы останутся линейно независимыми и потому образуют фундаментальную систему решений для исходной системы.

Пусть дана система линейных уравнений $A\mathbf{x} = \mathbf{b}$ с $n$ неизвестными. 1. Элементарными преобразованиями строк приводим матрицу $A|b$ к ступенчатому виду 2. Если ранг $r$ матрицы $A$ меньше ранга матрицы $A|b$, система $A\mathbf{x} = \mathbf{b}$ несовместна. Если ранги равны, находим частное решение $\mathbf{x}_{0}$ этой системы 3. Находим фундаментальную систему решений $\mathbf{x}_{1}, \dots, \mathbf{x}_{n-r}$ соответствующей однородной системы $A\mathbf{x} = 0$ 4. Выражение $\mathbf{x} = \mathbf{x}_{0} + c_{1} \mathbf{x}_{1} + c_{2} \mathbf{x}_{2} + \dots + c_{n-r} \mathbf{x}_{n-r}$, где $c_{1}, c_{2}, \dots, c_{n-r}$ - произвольные скаляры, даёт **общее решение** системы $A\mathbf{x} = \mathbf{b}$. Каждое решение системы получается из общего при некотором (однозначно определяемом) наборе $c_{1}, c_{2}, \dots, c_{n-r}$ Сложность такой процедуры $O(n^{3})$, где $n$ - число уравнений.